package com.fzy.leetcode.editor.cn;
//2023-03-23 14:12:57
//给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 
//
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。 
//
// 
//
// 示例 1： 
// 
// 
//输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//输出：4 
//解释：最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2： 
// 
// 
//输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
//输出：4 
//解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
//
// 示例 3： 
//
// 
//输入：matrix = [[1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 200 
// 0 <= matrix[i][j] <= 2³¹ - 1 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 数组 动态规划 矩阵 👍 748 👎 0

class LongestIncreasingPathInAMatrix {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new LongestIncreasingPathInAMatrix().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m+1][n+1];
        int ans = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                ans = Math.max(ans,backtracking(matrix,dp,i,j));
            }
        }
        return ans;
    }

    public int backtracking(int[][] matrix,int[][] dp,int i,int j){
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        dp[i][j]++;

        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

        for(int dir[] : dirs){
            int newi = i+dir[0];
            int newj = j+dir[1];

            if(newi >= 0 &&newi<matrix.length && newj >= 0 && newj < matrix[0].length && matrix[newi][newj] > matrix[i][j]){
                dp[i][j] = Math.max(dp[i][j],backtracking(matrix,dp,newi,newj)+1);
            }
        }
        return dp[i][j];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}